/*
 * Copyright (c) 2011 Robert Kirchgessner <rkirchge@gmail.com>
 *                    Carlo Pascoe <carlo.pascoe@gmail.com>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include <stdlib.h>
#include <sys/queue.h>
#include <assert.h>

#include "graph.h"
#include "randgraph.h"

static struct edge *
_markov_graph_get_random_edge(struct vertice *v)
{
  struct edge **e_list, *e;

  uint32_t allocated = 10;
  e_list = (struct edge **)malloc(sizeof(struct edge *)*allocated);
  assert(e_list != NULL);

  uint32_t count = 0;
  LIST_FOREACH(e, &v->edges, next) {
    e_list[count++] = e;
    if(count == allocated) {
      allocated = 2*allocated;
      e_list = realloc(e_list, sizeof(struct edge *)*allocated);
    }
  }

  if(count == 0) {
    free(e_list);
    return NULL;
  }

  e = e_list[rand()%count];
  free(e_list);
  return e;
}

static uint32_t
_markov_graph_swap_edge(struct vertice *v0, struct vertice *v1)
{
  struct edge *e0, *e1;
  struct vertice *v_tmp;

  if(v0 == v1) {
    return 0;
  }

  e0 = _markov_graph_get_random_edge(v0);
  e1 = _markov_graph_get_random_edge(v1);

  if(e0 == NULL || e1 == NULL) {
    return 0;
  }

  if(e0->v == e1->v || e0->v == v1 || e1->v == v0) {
    return 0;
  }

  //Swap the edge
  v_tmp = e0->v;
  e0->v = e1->v;
  e1->v = v_tmp;
  return 1;
}

uint32_t
markov_rand_graph(struct graph *g, uint32_t *adj, struct graph *rg, uint32_t q)
{
  struct vertice *v, **v_list;
  uint32_t index, count;

  /*Duplicate existing graph*/
  graph_copy(g, adj, rg);

  v_list = (struct vertice **)malloc(rg->size * sizeof(struct vertice *));
  assert(v_list != NULL);

  //Build a linear vertice list (for easier access)
  index = 0;
  LIST_FOREACH(v, &rg->vertices, next) {
    v_list[index++] = v;
  }

  uint32_t selected0, selected1;

  index = 0;
  //Perform the randomization
  for(count=0; count< q * rg->edges; count++) {
     selected0 = rand()%rg->size;
     selected1 = rand()%rg->size;
    index += _markov_graph_swap_edge(v_list[selected0], v_list[selected1]);
  }

  free(v_list);
  return index;
}

